package com.demo.jzoffer2;

import org.junit.Test;

/**
 * @author gy
 * @date 2023/04
 */
public class Test0407_01 {

    /**
     * 寻找 . 数字序列中某一位的数字  数位的数字是多少
     *
     * 数字以0123456789101112131415…的格式序列化到一个字符序列中。在这个序列中，
     * 第5位（从下标0开始计数）是5，第13位是1，第19位是4，等等。
     *
     * 请写一个函数，求任意第n位对应的数字。
     *
     * 示例 1：
     *
     * 输入：n = 3
     * 输出：3
     * 示例 2：
     *
     * 输入：n = 11
     * 输出：0
     *
     *
     * 限制：
     *
     * 0 <= n < 2^31
     *
     * 思路分析：
     * 1、将 101112⋯101112 中的每一位称为 数位 ，记为 n ；
     * 2、将 10,11,12,⋯ 称为 数字 ，记为 num ；
     * 3、数字 10 是一个两位数，称此数字的 位数 为 2 ，记为 digit ；
     * 4、每 digit 位数的起始数字（1、10、100） 记为 start
     *
     * 位数递推公式  digit = digit + 1
     * 起始数字递推公式 start = start * 10
     * 数位数量计算公式 count = 9 * start * digit
     *
     * 依据以上分析：求解分为三步：
     * 1、确定n所在数字的位数 digit  1位数 2位数 3位数
     * 2、确定n所在的数字 num
     * 3、确定num中的哪一数位，并返回结果
     * @param n
     * @return
     */
    public int findNthDigit(int n) {
        if(n==0) {
            return 0;
        }
        //由于是n=0时对应开始的0，这里不需要进行减操作n--;，但是如果n=1对应开始的0则需要减操作
        //排除n=0后，后面n从1开始。
        int digit = 1;
        int start = 1;
        long count = 9; //count的值有可能会超出int的范围，所以变量类型取为long
        while(n>count){//不能带=号，此时n从1开始，n=count时，属于上一个循环的最后一个数字
            n=(int)(n-count);//这里(int)不能省略
            digit++;
            start = start*10;
            count = (long)start*9*digit;
            //这里的long不能省略，否则，会先按照int类型进行计算，然后赋值给long型的count，超过int大小限制时，会出现负数
        }

        int num = start + (n-1)/digit;
        int index = (n-1)%digit;//index最大取digit-1,即此时num坐标从左到右为0,1,...,digit-1,共digit位
        while(index<(digit-1)){
            //最后的结果是num中的第index个数字，index从左到右从0开始递增，考虑到踢出右侧末尾的数字比较简单，我们从右侧开始依次踢出数字
            num = num/10;
            digit--;
        }
        return num%10;//此时num的右侧末尾数字即为结果
    }

    @Test
    public void m1() {

    }

    @Test
    public void m2() {

    }

    @Test
    public void m3() {

    }

}
